CSE 311: Section 3

Task 1 – This is Really Mod

Let $n$ and $m$ be positive integers.

Consider the following claim: for any integers $a$ and $b$, if $a \equiv_m b$, then $a \equiv_n b$.

1. Write a formal proof that the claim holds, given that $n\ |\ m$.

   Hint: the claim to prove is $\forall a\, \forall b\, ((a \equiv_m b) \to (a \equiv_n b))$. The fact we are given is that $n\ |\ m$.

2. Translate your formal proof to an English proof.

Task 2 – Extended Euclidean Algorithm Practice

1. Find the multiplicative inverse of $y$ of 7 mod 33. That is, find $y$ such that $7y \equiv 1 (\text{mod } 33)$, You should use the extended Euclidean Algorithm. Your answer should be in the range $0 \leq y < 33$.

2. Now solve $7z \equiv 2$ (mod 33) for all of its integers solutions $z$.

Task 3 – Induction with Equality

For all $n \in \mathbb{N}$, prove by induction that $\displaystyle \sum_{i=0}^n i^2 = \frac{1}{6}n(n+1)(2n+1)$.

Task 4 – Strong Induction

Consider the function $a(n)$ defined for $n \geq 1$ recursively as follows. $$a(1) = 1$$ $$a(2) = 3$$ $$a(n) = 2a(n-1) - a(n-2) \text{ for } n \geq 3$$ Use strong induction to prove that $a(n) = 2n - 1$ for all integers $n \geq 1$.